package 剑指Offer.easy;

public class 二叉树的最近公共祖先 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution1 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            while (root != null) {
                if (p.val > root.val && q.val > root.val) {//都在右子树
                    root = root.right;
                } else if (p.val < root.val && q.val < root.val) {//都在左子树
                    root = root.left;
                } else {
                    break;
                }
            }
            return root;
        }
    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            int min = p.val, max = q.val;
            if (min > max) {
                int tmp = min;
                min = max;
                max = tmp;
            }
            while (root != null) {
                if (min > root.val) {
                    root = root.right;
                } else if (max < root.val) {
                    root = root.left;
                } else {
                    break;
                }
            }
            return root;
        }
    }
}
